package study1;

import java.util.*;

public class PreorderTraversal {
    static class TreeNode {
        public int val;         // 节点存储的字符值
        public TreeNode left;    // 左子节点引用
        public TreeNode right;   // 右子节点引用

        public TreeNode(int val) {
            this.val = val;      // 构造函数初始化节点值
        }
    }


    /**递归前序遍历（直接打印）
     特点：
        遍历顺序：根 → 左 → 右（前序）。
        缺点：结果直接打印，无法返回集合供后续使用。
     适用场景：快速调试或简单打印场景


     * */
    public void preOrder(TreeNode root) {
        if (root == null) return;       // 递归终止条件：空节点
        System.out.print(root.val + " "); // 访问根节点
        preOrder(root.left);             // 递归遍历左子树
        preOrder(root.right);            // 递归遍历右子树
    }


    /**递归前序遍历（返回集合） 面试经典
     核心优化：通过参数传递结果集合
     变量分析：
     root：二叉树的根节点（可能为null表示空树）。
     list：创建空的 ArrayList<Integer>，用于存储前序遍历结果。
     执行流程：
        1. 初始化空列表 list。
        2. 调用双参数递归方法 preorder(root, list)，传入根节点和空列表。
        3. 返回递归处理后的列表（此时已填充遍历结果）。
     空间复杂度：O(h)（h为树高）
     优点：
        代码简洁，符合前序遍历定义。
        返回结果集合，便于后续操作（复用）。
     缺点：
        递归深度大时可能导致栈溢出。
     * */
    // 单参数的入口方法
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();// 创建空列表
        return preorder(root, list);// 调用双参数递归方法
    }
    // 双参数的递归方法
    /**
     * 功能：递归实现前序遍历（根 → 左 → 右）。
     * 参数分析：
     * root：当前处理的节点（递归中变化）。
     * list：累积遍历结果的列表（始终是同一个列表对象的引用）。
     */
    private List<Integer> preorder(TreeNode root, List<Integer> list) {
        // 递归终止条件：当当前节点为 null（叶子节点的子节点/空树），直接返回当前列表，结束递归分支。
        if (root == null) return list;
        list.add(root.val); // 将当前节点的值加入列表
        //递归左子树：传入当前节点的左子节点（root.left）和列表。
        preorder(root.left, list);
        //递归右子树：传入当前节点的右子节点（root.right）和列表。
        preorder(root.right, list);
        return list;
    }


    /**基于栈的迭代方法（显式栈）    面试经典
     核心思想：用栈模拟递归过程
     变量分析：
        result：存储遍历结果的列表。
        stack：显式栈（Stack<TreeNode>），管理待访问节点。
        node：当前弹出的节点。

     执行流程：
     1. 初始化：根节点入栈。
     2. 循环处理（栈非空时）：
            弹出栈顶节点 node。
            将 node.val 加入 result（访问根节点）。
            右子节点先入栈（保证左子节点先被处理）。
            左子节点后入栈（栈的 LIFO 特性确保优先处理）。

     关键逻辑分析
     入栈顺序（先右后左）：
        原因：栈是 LIFO（后进先出） 结构。
        右子节点先入栈 → 被压在栈底，最后处理。
        左子节点后入栈 → 位于栈顶，优先弹出处理。
        效果：实现 根→左→右 的遍历顺序。
     弹出即访问：
        每次弹出节点时立即将其值加入 result，符合前序遍历 先访问根节点 的特性。
     边界处理：
        空树检查：if (root == null) 直接返回空列表，避免空指针异常。
        叶子节点：无子节点时不进行入栈操作，循环自然终止。

     算法特点
        时间复杂度：O(n)
        每个节点恰好进出栈各一次，访问一次。
        空间复杂度：O(n)
        最坏情况（树退化为链表）时栈深度为 n。

     优势：避免递归的栈溢出风险，适合深层次二叉树，面试推荐使用。
     * */


    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();  // 存储遍历结果
        if (root == null) return result;          // 边界条件：空树直接返回

        Stack<TreeNode> stack = new Stack<>();    // 显式栈存储待处理节点
        stack.push(root);                         // 初始化：根节点入栈

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();          // 1. 弹出当前节点
            result.add(node.val);                 // 2. 访问当前节点（根）

            // 3. 右子节点先入栈（保证左子节点先处理）
            if (node.right != null) stack.push(node.right);
            // 4. 左子节点后入栈（后进先出，下次循环优先弹出）
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }



    /**迭代（显式栈 - 中序模板修改版）
     算法逻辑
     前序遍历顺序：根节点 → 左子树 → 右子树。
     核心思想：使用显式栈（Stack）模拟递归的隐式调用栈。

     关键操作：
     从根节点开始，优先访问当前节点（添加到结果列表）。
     沿左子树深度优先向下遍历，将路径上的节点压入栈。
     左子树访问完毕后，弹出栈顶节点，转向其右子树重复上述过程。

     执行过程
     1. 初始化：
     结果列表 ret 存储遍历结果。
     栈 stack 辅助节点回溯。
     当前节点 cur 指向根节点 root。

     2. 主循环（while (cur != null || !stack.isEmpty())）：
     （1） 向左子树深入（内层 while 循环）：
     若 cur != null，访问当前节点值（ret.add(cur.val)），将其压栈。
     更新 cur = cur.left（深入左子树）。
     （2） 回溯并转向右子树：
     当 cur 为空（左子树尽头），弹出栈顶节点 top。
     将 cur 指向 top.right（处理右子树）。
     3. 终止条件：栈空且 cur 为 null（所有节点处理完毕）


     变量分析
     变量	        类型	                    作用
     ret	    List<Integer>	    存储前序遍历结果（根 → 左 → 右）。
     stack	    Stack<TreeNode>	    暂存未处理右子树的节点（模拟递归回溯）。
     cur	    TreeNode	        当前访问节点：
     - 非空时：访问节点并深入左子树。
     - 空时：触发回溯。
     top	    TreeNode	        栈顶节点（回溯时弹出），用于定位右子树。



     适用场景
     场景类型	                                说明
     深度优先遍历	            适合需要优先处理父节点再访问子节点的场景（如复制树结构、表达式树求值）。
     避免递归缺陷	            栈深度可控，避免递归的栈溢出（适用于深度极大的树）。
     空间复杂度优化	        空间复杂度为 O(h)（h 为树高），优于递归的 O(n) 栈帧开销。
     非递归需求	            需显式控制遍历流程的场景（如嵌入式系统限制递归调用）。


     * */

    public List<Integer> preorderTraversal3(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                //System.out.print(cur.val + " ");
                ret.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return ret;
    }



    /**基于栈的迭代方法（显式栈）方法二
     核心思想：模拟递归调用栈
     变量分析：
        res：存储遍历结果的列表。
        stack：双端队列（Deque）模拟的栈，存储回溯路径。
        node：当前处理的节点指针。

     执行流程：
     1. 向左深入，边访问边入栈
            访问当前节点（res.add(node.val)）。
            节点入栈（记录回溯点）。
            转向左子节点（node = node.left）。
     2. 回溯处理：
            当左子树到底时（node == null），弹出栈顶节点（父节点）。
            转向其右子树（node = node.right）。

     优点：
        符合递归思维（显式模拟递归栈）。
        统一处理逻辑，适合前序/中序/后序的迭代实现。
     缺点：
        空间复杂度与树高相关（最坏 O(n)）。

     对比上一个方法：本质相同，是上一个方法的简洁写法。
     * */
    public List<Integer> preorderTraversal4(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<>();// 双端队列模拟栈
        TreeNode node = root;// 当前节点指针
        while (!stack.isEmpty() || node != null) {
            while (node != null) {           // 深入左子树
                res.add(node.val);            // 访问当前节点（根）
                stack.push(node);             // 节点入栈（用于回溯）
                node = node.left;             // 转向左子节点
            }
            node = stack.pop();               // 回溯到父节点
            node = node.right;                // 转向右子树
        }
        return res;
    }





    /**
     Morris 遍历
     思路与算法
     有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。
     Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：
        1. 新建临时节点，令该节点为 root；
        2. 如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
        3. 如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
            如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
            如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
        4. 重复步骤 2 和步骤 3，直到遍历结束。


     核心突破：O(1)空间复杂度

     变量分析：
        res：存储遍历结果的列表。
        p1：当前遍历的节点。
        p2：辅助指针，用于定位 p1 的前驱节点（左子树的最右节点）。


     执行流程：
        1. 无左子树：直接访问 p1，转向右子树。
        2. 有左子树：
            首次访问（p2.right == null）：
                访问 p1（res.add(p1.val)）。
                建立线索：p2.right = p1（将前驱节点的右指针指向 p1）。
                深入左子树（p1 = p1.left）。
            二次访问（p2.right == p1）：
                断开线索：p2.right = null。
                转向右子树（p1 = p1.right）。


     核心思想：
     1. 线索化：利用叶子节点的空指针指向后继节点，避免栈的使用。
     2. 两次访问：
        首次访问：建立线索，访问节点（前序时机）。
        二次访问：断开线索，转向右子树。

     优点：
        空间复杂度 O(1)（仅用两个指针），极致空间优化
        无需递归或显式栈。
     缺点：
        临时修改树结构（最后恢复）。
        逻辑复杂，调试困难。
     * */


    public List<Integer> preorderTraversal5(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        TreeNode p1 = root; // 当前节点指针
        TreeNode p2 = null; // 辅助指针（寻找前驱节点）

        while (p1 != null) {
            p2 = p1.left;
            if (p2 != null) {
                // 找到 p1 的左子树的最右节点（前驱）
                while (p2.right != null && p2.right != p1) {
                    p2 = p2.right;
                }
                if (p2.right == null) { // 首次访问 p1
                    res.add(p1.val);    // 访问当前节点
                    p2.right = p1;      // 建立线索（指向 p1）
                    p1 = p1.left;       // 深入左子树
                    continue;           // 跳过后续代码
                } else {                // 二次访问 p1
                    p2.right = null;    // 断开线索
                }
            } else { // 无左子树
                res.add(p1.val);        // 直接访问
            }
            p1 = p1.right; // 转向右子树
        }
        return res;
    }





    /**
     颜色标记法
     方法原理
        核心思想：用状态标记区分未访问/已访问节点
        数据结构：栈存储(节点, 状态)元组
            状态=0：未访问
            状态=1：已访问（可输出值）

     方法优势
     1. 逻辑统一：前/中/后序遍历只需调整入栈顺序
            前序：右→左→根
            中序：右→根→左
            后序：根→右→左
     2. 直观易懂：显式状态标记降低理解难度
     3. 无递归限制：避免栈溢出风险


     关键变量分析
     变量名	                        类型	                               作用
     result	                     List<Integer>	             存储前序遍历结果（动态数组）

     stack	                     Deque<Object[]>	         模拟递归栈：
                                                              - 存储[节点, 状态]元组
                                                              - 使用ArrayDeque提升性能

     item	                     Object[2]	                 栈元素：
                                                              - item[0]：TreeNode节点
                                                              - item[1]：Integer状态值

     node	                     TreeNode	                 当前处理的二叉树节点

     status	                     int	                     节点状态标记：


     算法特点分析
     1. 时间复杂度：O(n)
        每个节点恰好入栈1次（状态0）
        每个节点恰好出栈2次（状态0弹出+状态1弹出）
     2. 空间复杂度：O(n)
        最坏情况（左斜树）：栈深度=n
        平均情况：栈深度≈树高
     3. 核心优势：
        逻辑统一：只需调整入栈顺序即可实现前/中/后序遍历                                                         - 0：未访问
        避免递归：不受调用栈深度限制
        状态可见：调试时清晰观察节点处理阶段                                                     - 1：已访问
     4. 对比传统迭代法：
        传统迭代法	                        颜色标记法
        需单独处理节点访问时机	           状态值显式控制访问时机
        前/中/后序实现逻辑差异大	       三序遍历仅需调整入栈顺序
        回溯逻辑复杂	                   状态机模型更符合人类思维

     * */

    public List<Integer> preorderTraversal6(TreeNode root) {
        // 存储遍历结果的动态数组
        List<Integer> result = new ArrayList<>();

        // 空树直接返回
        if (root == null) return result;

        // 使用双端队列模拟栈（效率高于Stack类）
        // 每个栈元素是Object[2]数组：[0]=节点对象, [1]=状态值(Integer)
        Deque<Object[]> stack = new ArrayDeque<>();

        // 初始状态：根节点未访问（状态0）入栈
        stack.push(new Object[]{root, 0});

        // 栈非空时循环处理
        while (!stack.isEmpty()) {
            // 弹出栈顶元素（最新入栈的元素）
            Object[] item = stack.pop();
            TreeNode node = (TreeNode) item[0];   // 解包节点对象
            int status = (Integer) item[1];       // 解包状态值

            if (status == 1) {
                // 状态1：已访问节点 → 直接加入结果集
                result.add(node.val);
            } else {
                /* 状态0：新节点 → 按反向顺序入栈（栈LIFO特性） */
                // 1. 右子节点（未访问）入栈 → 最后处理
                if (node.right != null) {
                    stack.push(new Object[]{node.right, 0});
                }
                // 2. 左子节点（未访问）入栈 → 优先处理
                if (node.left != null) {
                    stack.push(new Object[]{node.left, 0});
                }
                // 3. 当前节点标记为已访问（状态1）入栈 → 最先弹出处理
                stack.push(new Object[]{node, 1});
            }
        }
        return result;
    }
}
/*
方法	                优点	                        缺点	                空间复杂度	    适用场景
递归（直接打印）	    代码简洁	                    结果无法复用	        O(h)	        简单调试
递归（返回集合）	    结果可复用，符合遍历定义	        深度大时栈溢出	        O(h)	        小规模树
迭代（显式栈 - 方法1）	避免递归栈溢出，逻辑清晰	        额外栈空间	        O(n)	        深层次树
迭代（中序模板修改版）  与前/后序共享迭代框架         回溯逻辑稍复杂	        O(h)            需统一遍历框架的工程实现
迭代（显式栈 - 方法2）	统一处理前/中/后序，模拟递归	    空间与树高相关	        O(h)	        需统一迭代逻辑的场景     是上一个方法的简洁写法
Morris 遍历	        O(1) 空间，无栈无递归	        修改树结构，逻辑复杂	O(1)	        空间敏感的大规模树
颜色标记法	        逻辑清晰，三序遍历代码统一	    需额外存储状态	        O(n)	        需高可读性/统一实现场景



选择建议：
面试优先推荐迭代显式栈（方法1）或颜色标记法
竞赛/大规模数据考虑Morris遍历
日常开发递归（集合）版本简洁够用
* */



/*补充：空间敏感的大规模树：深度解析
1. 概念定义
空间敏感（Space-Sensitive）：
指内存资源受限的场景，要求算法必须严格限制额外空间使用。常见于：
    嵌入式设备（IoT设备、传感器）
    实时操作系统（航空航天、汽车控制系统）
    超大规模数据处理（数十亿节点）
    内存严格受限的微服务（Serverless环境）

大规模树（Large-Scale Tree）：
通常指节点数量达到：
    10⁶ 级（百万节点）：传统栈方法消耗 ~8MB 内存（假设指针8字节）
    10⁹ 级（十亿节点）：递归/栈方法需 ~8GB 内存，远超普通设备容量

2. Morris遍历的核心价值
空间复杂度 O(1)：
仅需2个指针变量（p1, p2），不依赖栈/递归

内存消耗对比：
方法	        10⁶节点内存	10⁹节点内存	是否可行
递归	        ~8MB	    ~8GB	      ❌
显式栈迭代	~8MB	    ~8GB	      ❌
Morris遍历	~16字节	    ~16字节	      ✅

实际案例：
处理10亿节点树时：
    传统方法：需要8GB内存（相当于高端服务器配置）
    Morris：仅需16字节（任何设备均可运行）


    */